/**
 * @description：合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array/description/?envType=problem-list-v2&envId=sorting
 * @author: yangyahui01
 * @date: 12/27/24 6:33 PM
 */
public class 合并两个有序数组 {

    /**
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     */

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};

        merge(nums1, 3, nums2, 3);

        for (int i : nums1) {
            System.out.print(i + " ");
        }
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {

        // 从后向前遍历?
        int k = m + n - 1; //总长度

        int p1 = m - 1; //nums1的指针
        int p2 = n - 1; //nums2的指针

        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] >= nums2[p2]) {
                nums1[k] = nums1[p1];
                p1--;
            } else {
                nums1[k] = nums2[p2];
                p2--;
            }
            k--;
        }

        // 这个不需要执行，因为不需要把 nums1剩余的元素再原地复制给自己一份了
       /* while (p1 >= 0) {
            nums1[k--] = nums1[p1--];
        }*/

        while (p2 >= 0) {
            nums1[k--] = nums2[p2--];
        }
    }
}
